package com.littleshu.test;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。 <br/>
 * 程序分析：对n进行分解质因数，应先找到一个最小的质数k <br/>
 * 
 * @author littleshu
 *
 */
public class Question4 implements RunTest {
	
	public static void main(String[] args) {
		new Question4().runTest();
	}

	@Override
	public void runTest() {
		SeparetePrimeFactorNum num = new Number(90);
		num.separete();
	}

	class Number implements SeparetePrimeFactorNum {
		List<Integer> factorList = new ArrayList<Integer>();
		int num;

		Number(int num) {
			this.num = num;
		}

		@Override
		public void separete() {
			getFactor(num);
			StringBuffer sbf = new StringBuffer();
			sbf.append(num).append(" = ");
			for (Integer n : factorList) {
				sbf.append(n).append(" * ");
			}
			sbf = sbf.delete(sbf.length() - 2, sbf.length() - 1);
			System.out.println(sbf.toString());
		}

		/**
		 * 分解质因数的核心计算
		 * 
		 * @param num
		 */
		private void getFactor(int num) {
			for (int i = 2; i < num; i++) {
				// 一旦得到质因数，就将其放入list接着递递归分解后的值
				if (num % i == 0) {
					factorList.add(i);
					getFactor(num / i);
					return;
				}
			}
			// 剩下的最后一个分解的值也属于质因数，因此加入集合
			factorList.add(num);
		}

	}
}

interface SeparetePrimeFactorNum {
	public void separete();
}
